package com.LeeCode;

import java.util.ArrayList;

/**
 * 对角线遍历
 */

public class Code498 {
    public static void main(String[] args) {

    }

    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) return new int[0];
        int m = mat.length, n = mat[0].length;
        int[] res = new int[m * n];
        int idx = 0;

        // 遍历每一条对角线，k 表示对角线编号（从 0 开始）
        for (int k = 0; k <= m + n - 2; k++) {
            // 从该对角线的起点开始向下/向左遍历：起点可取第一行或最后一列
            int r = (k < n) ? 0 : k - (n - 1);
            int c = (k < n) ? k : n - 1;

            // 临时存放当前对角线的元素
            ArrayList<Integer> temp = new ArrayList<>();
            while (r < m && c >= 0) {
                temp.add(mat[r][c]);
                r++;
                c--;
            }

            // 偶数编号对角线需要逆序加入结果，奇数编号按顺序加入
            if (k % 2 == 0) {
                for (int i = temp.size() - 1; i >= 0; i--) {
                    res[idx++] = temp.get(i);
                }
            } else {
                for (int v : temp) {
                    res[idx++] = v;
                }
            }
        }

        return res;
    }
}
